package leetcode.array;

import leetcode.Hot100.productExceptSelf;
import leetcode.Hot100.singleNumber;

import java.util.Arrays;
import java.util.HashSet;

/**
 * @author Cheng Jun
 * Description: 给定一个包含 [0, n] 中 n 个数的数组 nums ，找出 [0, n] 这个范围内没有出现在数组中的那个数。
 * https://leetcode-cn.com/problems/missing-number/
 * @version 1.0
 * @date 2022/2/17 17:45
 */
public class missingNumber {

    public static void main(String[] args) {

    }

    // 思路：排序，然后比较 i 和 nums[i]
    // 时间复杂度O(n) = nlogn, 空间复杂度 O(1)
    public static int missingNumber(int[] nums) {
        Arrays.sort(nums);
        for (int i = 0; i < nums.length; i++) {
            if (i != nums[i]) {
                return i;
            }
        }
        return nums.length;
    }

    // 思路：利用 Hashset
    // 时间复杂度O(n) = n, 空间复杂度 O(n)
    public static int missingNumber1(int[] nums) {
        int length = nums.length;
        // nSet 包含 [0, n]
        HashSet<Integer> nSet = new HashSet<>();
        for (int i = 0; i <= length; i++) {
            nSet.add(i);
        }
        for (int num : nums) {
            nSet.remove(num);
        }
        // 返回缺失的数字
        for (Integer missNum : nSet) {
            return missNum;
        }
        // 此处return在这个题解中不会执行，只是为了保证语法逻辑的完成整性
        return length;
    }

    // 思路：由小学三年级的知识可得知 0 + 1 + ··· + n = (1 + n) * n / 2
    // 时间复杂度O(n) = n, 空间复杂度 O(1)
    public static int missingNumber2(int[] nums) {
        int length = nums.length;
        int sum = (1 + length) * length / 2;
        for (int num : nums) sum -= num;
        return sum;
    }

    /**
     * 受到 singleNumber(136. 只出现一次的数字) 的异或运算符启发
     * 可以将 nums[i] 和 [0, n] 异或 得到 missNum
     * @author Cheng Jun
     * @date 2022/2/18 9:28
     * @param nums
     * @return int
     * @see singleNumber
     */
    public static int missingNumber3(int[] nums) {
        int res = nums.length;
        for (int i = 0; i < nums.length; i++) res ^= i ^ nums[i];
        return res;
    }
}
